import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
class IntCmp implements Comparator<Integer>{


    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class Main {
    public static void shiftDown(int[] array,int rootval,int len){
        int parent = rootval;
        int child = 2*parent+1;
        while(child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[parent]<array[child]){
                int tem = array[parent];
                array[parent] = array[child];
                array[child] = tem;
                parent++;
                child = 2*parent+1;
            }else{
                break;
            }
        }

    }
    public static void createHeap(int[] array){
        for(int i = (array.length-1-1)/2;i>=0;i--){
            shiftDown(array,i,array.length);
        }
    }
    public static void shell(int[] array,int gap){
        for(int i = gap;i<array.length;i++){
            int tem = array[i];
            int j =i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>tem){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tem;
        }

    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);


    }
    public static void insertSort(int[] array){
        for(int i = 1;i< array.length;i++){
            int index = i;
            for(int j = i-1;j>=0;j--){
                if(array[index]<array[j]){
                    int tem = array[index];
                    array[index] = array[j];
                    array[j] = tem;
                    index--;
                }
            }
        }
    }
    public static void bubble(int[] array){
        int lastIndex = array.length-1;
        int swapIndex = -1;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int i = 0;i<lastIndex;i++){
                if(array[i]>array[i+1]){
                    swap(array,i,i+1);
                    flag = true;
                    swapIndex = i;
                }
            }
            lastIndex = swapIndex;
        }
    }
    private static void swap(int[] array,int x,int y){
        array[x] = array[x]^array[y];
        array[y] = array[x]^array[y];
        array[x] = array[x]^array[y];
    }
    public static void main(String[] args) {
        int[] array = new int[]{5,3,8,92,3,1,9};
        shellSort(array);
        System.out.println(Arrays.toString(array));

    }

    public static void main1(String[] args) {
        HashMap<Integer,Integer> map = new HashMap<>();
        System.out.println(map.get(9));

    }



    public static int[] topk(int k,int[] array){
        IntCmp in = new IntCmp();
        PriorityQueue<Integer> queue = new PriorityQueue<>(k,in);
        for(int i = 0;i<array.length;i++){
            if(i<k){
                queue.offer(array[i]);
            }else{
                int top = queue.peek();
                if(array[i]<top){
                    queue.poll();
                    queue.offer(array[i]);
                }
            }
        }
        int[] ret = new int[k];
        for(int i = 0;i<k;i++){
            ret[i] = queue.poll();
        }
        return ret;


    }
}
